The present invention relates to a system for displacement vector searching in digital image analysis, and more particularly to a displacement vector searching system of the type wherein pixel data for two successive images are divided into a regular block grid, the pixel data including digitalized gray values for the pixels, and wherein the blocks are used to determine displacement of associated blocks in the successive images by forming sums of the amount differences of subquantities of the pixel data of associated blocks, determining the minimum of these sums to find the best correlation of gray value peaks, and from this determining the displacement vectors of the blocks.
For the transmission of video scenes by telephone at transmission rates between 64 kbit/s and 384 kbit/s, prediction coding methods are employed. Prediction coding utilizes the information already existing at the receiver to describe the current image with the least amount of information. Prediction coding is improved considerably if the changes from image to image due to movement in the scene are detected in space and time and are included in the calculation of the predicted image (prediction coding with motion compensation). Prior art methods for motion compensation are, for example, the block-wise motion compensation disclosed in European Patent application No. 0,123,616 and the object specific motion compensation disclosed, for example, in German Offenlegungsschrift (unexamined published application) No. 3,328,341. These methods have in common that two images composed of digitalized pixels for luminance and chrominance are compared with one another essentially pixel by pixel. For this purpose, the digitalized images are divided into regular block grids.
In block-wise motion compensation, the entire image to be predicted is processed schematically (iconic image processing). Each n-pixel by n-pixel (that is, n x n) block of the regular block grid has an associated image-to-image displacement, in which a distance measure between the gray value peaks of the current block and the gray value peaks of a correspondingly displaced block in the preceding image is at a minimum or in which a measure of similarity between the grey value peaks of the current block and the gray value peaks of a correspondingly displaced block in the preceding image is at a maximum.
For object specific motion compensation, adjacent moving (displaced) blocks are combined into so-called objects and their movement is described by at least one motion vector (displacement vector) which characterizes the movement of the object.
Finding the block displacement on the basis of a minimum distance measure will be explained in more detail with reference to FIGS. 1A through 1C. In FIG. 1A, the screen 100 of a cathode ray tube displays a rapid sequence of images. The currently-displayed image is divided into blocks such as block 102 by an imaginary grid 104, only a portion of which is shown. Imaginary grid lines 106, 108, 110, and 112 border block 102 and separate it from adjacent blocks. Block 102 has n rows and n columns of pixels.
In FIG. 1B, a concentric subquantity of the block 102 in the current image (hereafter referred to as measuring window 114) is determined. Measuring window 114 has s rows and s columns of pixels (where s.ltoreq.n), although only pixel 116 (at position 0,0 within measuring window 114), pixel 118 (at position 1,0) pixel 120 (at position s-1,0), pixel 122 (at position 0, s-1), pixel 124 (at position s-1, s-1), and pixel 126 (at an arbitrary position i,k, where the index i identifies a column and the index k identifies a row) are shown. Reference number 128 designates a search domain disposed around block 102, search domain 128 having 2q+s rows and 2q+s columns of pixels, and reference number 130 designates a test window which is moved within search domain 128. Like measuring window 114, test window 130 has s rows and s columns of pixels, although only pixel 132 (at position 0,0 within test window 130), pixel 134 (at position 1,0), pixel 136 (at position 0, s-1), and pixel 138 (at position s-1, s-1) are shown. However unlike measuring window 114, which represents pixels in the current image, test window 130 (and search domain 128) represents pixels of the prior image.
For each position of test window 130 within search domain 128, the gray values of the current-image pixels of measuring window 114 are compared with the gray values of the prior-image pixels of test window 130 to provide a sum V of the difference amounts. More precisely, for each test window position ##EQU1## In Equation (1), a.sub.ik is the digital gray value of the pixel in the current image, b.sub.ik is the digitalized gray value of the pixel in the preceding image, and the subscript "0" (in the term "V.sub.o ") refers the sum V when test window 130 is in its initial position in the center of block 102. In Equation 1 and elsewhere in the present application, the first index (i) indicates a column and the second index (k) indicates a row.
In view of Equation 1, when test window 130 is in the position as illustrated the sum V is found by summing the absolute value of the difference in gray values between pixel 116 and pixel 132, . . . , the absolute value of the difference in gray values between pixel 122 and pixel 136, the absolute value of the difference in gray values between pixel 118 and pixel 134, . . . , and the absolute value of the difference in gray values between pixel 124 and pixel 138. To find the next sum test window 130 is moved by one pixel to the right, for example, so that pixels 132 and 136 are no longer within test window 130, and pixel 134 becomes the prior-image pixel at position (0,0) within test window 130. The sum of the absolute values of the difference between gray values for the current and prior pixels is then found again in accordance with Equation 1. This procedure continues until test window 130 has been examined at every position within search domain 128, when the so-called full search is applied.
The search range defined by search domain 128 in the preceding image extends by .+-.q pixels in the x and y directions concentrically around the undisplaced measuring window 114. The distance value minimum to be found is one of (2q+1).sup.2 possible values ##EQU2## where the indices l and m are a function of the displacement of the measuring window.
Instead of using all pixels within a measuring window for the calculation of the sum of the differences, a subquantity selected according to the above sample may also be employed so that fewer calculation operations need to be performed.
By determining the minimum V=V.sub.min of the (2q+1).sup.2 values of V, a vector is defined which extends from the center of the block 102 in the current image to the center of the test window 130 of the prior image at some particular position of test window 130. In the example shown in FIG. 1C, it is assumed that V.sub.min occurs when test window 130 is positioned as illustrated. This represents the displacement of a block in two timely consecutive images. This vector is called the displacement vector V and the described method of finding the minimum of the distance measure of two blocks is called a displacement vector search.
While the foregoing discussion has been presented in terms of images which are being displayed on a screen, it will be apparent to those skilled in the art that the discussion is applicable in general to video information before it is displayed.